Bert Kappen
http://www.snn.ru.nl/~bertk/
Tuesday 27th November 2012
Time: 2pm
B10 Basement Seminar Room
Alexandra House, 17 Queen Square, London, WC1N 3AR
The Variational Garrote
In this talk, I present a new variational method for sparse regression using L0 regularization. The variational parameters appear in the approximate model in a way that is similar to Breiman's Garrote model. We refer to this method as the variational Garrote (VG). We show that the combination of the variational approximation and L0 regularization has the effect of making the problem effectively of maximal rank even when the number of samples is small compared to the number of variables. The VG is compared numerically with the Lasso method, ridge regression and the recently introduced paired mean field method (PMF). Numerical results on synthetic data show that the VG and PMF yield more accurate predictions and more accurately reconstruct the true model than the other methods. It is shown that the VG finds correct solutions when the Lasso solution is inconsistent due to large input correlations. For complex problems with correlated inputs the VG yields better results than the PMF. The naive implementation of the VG scales cubic with the number of features. By introducing Lagrange multipliers we obtain a dual formulation of the problem that scales cubic in the number of samples, but close to linear in the number of features.
.